#include <iostream>
#include <string>
#include <vector>

using namespace std;

/// @brief 哈希结点
/// @tparam K 键类型
/// @tparam V 值类型
template <class K, class V>
struct HashNode {
  HashNode<K, V>* _next;
  pair<K, V> _kv;
  HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
};

/// @brief 仿函数
/// @tparam T
template <class K>
struct HashFunc {
  size_t operator()(const K& key) { return key; }
};

/// @brief string类型特化
/// @brief string需要对其每一个字符计算hash
template <>
struct HashFunc<string> {
  size_t operator()(const string& s) {
    size_t hash = 0;
    for (auto c : s) {
      hash += c;
      hash *= 31;
    }
    return hash;
  }
};

/// @brief 哈希表
/// @tparam K 键类型
/// @tparam V 值类型
/// @tparam HashFunc
template <class K, class V, class hash = HashFunc<K>>
class HashTable {
  typedef HashNode<K, V> Node;

 public:
  size_t GetNextPrime(size_t prime) {
    // SGI
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes]{
        53,        97,         193,        389,       769,       1543,
        3079,      6151,       12289,      24593,     49157,     98317,
        196613,    393241,     786433,     1572869,   3145739,   6291469,
        12582917,  25165843,   50331653,   100663319, 201326611, 402653189,
        805306457, 1610612741, 3221225473, 4294967291};

    size_t i = 0;
    for (; i < __stl_num_primes; ++i) {
      if (__stl_prime_list[i] > prime) return __stl_prime_list[i];
    }

    return __stl_prime_list[i];
  }

  bool insert(const pair<K, V> kv) {
    // 检查是否出现过
    if (find(kv.first)) return false;
    hash gethash;
    // 扩容
    if (_n == _tables.size()) {
      size_t newsize = GetNextPrime(_tables.size());
      vector<Node*> newtables(newsize, nullptr);
      for (Node*& cur : _tables) {
        // 遍历链表
        while (cur) {
          Node* next = cur->_next;
          size_t hashi = gethash(cur->_kv.first) % newtables.size();
          cur->_next = newtables[hashi];
          newtables[hashi] = cur;
          cur = next;
        }
      }
      _tables.swap(newtables);
    }

    // 遍历并使用拉链法插入
    size_t hashi = gethash(kv.first) % _tables.size();
    Node* newnode = new Node(kv);
    Node* cur = _tables[hashi];
    // 头插
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    // 负载因子++
    _n++;
    return true;
  }

  bool Erase(const K& key) {
    Node* ret = find(key);
    if (!ret) return false;
    HashFunc<K> gethash;
    size_t hashi = gethash(key) % _tables.size();
    Node* cur = _tables[hashi];
    if (ret == cur) {
      // 头删
      cur = ret;
      _tables[hashi] = nullptr;
    } else {
      while (cur->_next != ret) {
        cur = cur->_next;
      }
      cur->_next = ret->_next;
    }
    delete ret;
    return true;
  }

  Node* find(const K& key) {
    if (!_tables.size()) return nullptr;
    hash gethash;
    size_t hashi = gethash(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur) {
      if (cur->_kv.first == key) {
        return cur;
      }
      cur = cur->_next;
    }
    return nullptr;
  }

 private:
  vector<Node*> _tables;
  size_t _n = 0;
};

int main(int argc, char const* argv[]) {
  /* code */
  return 0;
}
